//给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
//
// 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
//
//
//
// 示例 1：
//
//
//输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[[7,4,1],[8,5,2],[9,6,3]]
//
//
// 示例 2：
//
//
//输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
//输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
//
//
//
//
// 提示：
//
//
// n == matrix.length == matrix[i].length
// 1 <= n <= 20
// -1000 <= matrix[i][j] <= 1000
//
//
//
// Related Topics 数组 数学 矩阵 👍 1153 👎 0

package leetcode.editor.cn;

@SuppressWarnings("all")
//Java：旋转图像
public class 旋转图像 {
    public static void main(String[] args) {
        Solution solution = new 旋转图像().new Solution();
        // TO TEST

        int[][] matrix = {
                {5, 1, 9, 11},
                {2, 4, 8, 10},
                {13, 3, 6, 7},
                {15, 14, 12, 16}
        };

        solution.rotate(matrix);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        public void rotate(int[][] matrix) {
            if (matrix == null || matrix.length <= 1)
                return;
            int n = matrix.length;

            int temp;
            for (int i = 0; i < n / 2; i++) {
                for (int j = i; j < n - 1 - i; j++) {
                    move(matrix, i, j);
                }
            }
        }

        // (x,y) 位置的值会转到 (y,maxIndex-x)
        // maxIndex : 矩阵的长度-1,索引从0开始
        // n=3的矩阵 maxIndex=2,  (0,0)->(0,2) ,(1,0)->(0,1)
        private void move(int[][] matrix, int i, int j) {
            int max = matrix.length - 1;
            int x = j, y = max - i;
            int place = matrix[i][j];
            int temp = matrix[x][y];
            while (!(x == i && y == j)) {
                temp = matrix[x][y];//保存覆盖前的old值
                matrix[x][y] = place;//覆盖
                place = temp;  //下一个覆盖的值变为 覆盖前的old值
                // 更新找到下一个覆盖的坐标
                int x0 = x;
                x = y;
                y = max - x0;
            }
            matrix[x][y] = place;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
